package com.arron.algorithm.leetcodetop100.动态规划;

import java.util.Arrays;

/**
 *  打家劫舍一系列套路题解
 *   https://leetcode.cn/problems/house-robber-ii/solutions/67465/tong-yong-si-lu-tuan-mie-da-jia-jie-she-wen-ti-by-/
 */
public class 打家劫舍II {



    public int rob(int[] nums) {

        if (nums.length == 1){
            return nums[0];
        }

        if (nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(rob(nums,0,nums.length-2),rob(nums,1,nums.length-1));
    }

    public int rob(int[] nums,int start,int end){

        if (start >end){
            return 0;
        }
        return Math.max(rob(nums,start+2,end)+nums[start] , rob(nums,start+1,end));
    }



    public int rob_plus(int[] nums) {

        if (nums.length == 1){
            return nums[0];
        }

        if (nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(rob_plus(nums,0,nums.length-2),rob_plus(nums,1,nums.length-1));
    }

    //自底向上，动态规划
    public int rob_plus(int[] nums,int start,int end){


        int[] dp = new int[nums.length+2];

        for (int i = end; i >= start ; i--) {


            dp[i]  = Math.max(dp[i+2]+nums[i],dp[i+1]);

        }

        return dp[0];
    }


    public static void main(String[] args) {

        打家劫舍II rob = new 打家劫舍II();
        int[] nums = {2,7,9,3,1};
        rob.rob(nums);

    }

}
